package com.cacheserverdeploy.algorithm;

import java.util.ArrayList;
import java.util.List;

import com.cacheserverdeploy.node.ConsumeNode;
import com.cacheserverdeploy.node.Link;
import com.cacheserverdeploy.node.NetworkNode;
import com.cacheserverdeploy.util.Const;
import com.cacheserverdeploy.util.Util;

public class ThirdStep {

	public int adjust(List<Integer> severlocation, NetworkNode[] nodes, ConsumeNode[] consumeNodes) {
		SingleSourceDijkstra ssDijkstra = new SingleSourceDijkstra();
		
		int[] severs = new int[severlocation.size()];// 终点应该是服务器点
		for (int i = 0; i < severs.length; i++) {
			severs[i] = severlocation.get(i);
		}

		List<List<Integer>> severPaths = new ArrayList<>();// 消费点到服务器的最短路径
		//流量还原
		for (NetworkNode node : nodes) {
			node.restoreDischarge();
		}

//		System.out.println("---------------------------我是分割线----------------------");
		for (int i = 0; i < consumeNodes.length; i++) {			
			int start = consumeNodes[i].getNetworkNodeId();
			if (!nodes[start].isLocatedServer()) {
				// 有可能是服务器本身
				// 该点到其他所有点的最短距离

				// 这儿一定要注意，调用了最短函数之后，会修改本身的邻接矩阵
				int[][] matrix2 = Util.constructMatrix(nodes);
				List<List<Integer>> shortPaths = ssDijkstra.dijkstra_Path(matrix2, start, severs);
				// 该点到其他消费点最短路径，例如[43,44]
				List<Integer> shortestPath = ssDijkstra.findMinPath(shortPaths);
//				System.out.println(shortestPath.toString());
				// 全部存储下来
				severPaths.add(shortestPath);
			}
			
		}
		


		setDischarge(severPaths, nodes, consumeNodes, severlocation);// 设置流量

//		boolean hasNagetive = false;
//		int cyclenum = 0;
//		do {
//			hasNagetive = false;
//			for (NetworkNode node : nodes) {
//				List<Link> links = node.getLinks();
//				for (Link link : links) {
//					if (link.getExtraDischarge() < 0) {
//						hasNagetive = true;
//						break;
//					}
//				}
//			}

			for (NetworkNode node : nodes) {// 不需要考虑服务器点
				// if(!severGroup.contains(node.getId())){//不是服务器节点才需要考虑
				List<Link> links = node.getLinks();
				for (Link link : links) {
					if (link.getExtraDischarge() < 0) {// 如果有小于0链路，现在小于0的只有到消费点的
						int fromID = link.getFromId();// 比如0到6超限，0
						int toID = link.getToId();// 6

						// 这个地方得找到所有的用了这条超载路线的线路
						List<List<Integer>> subPath = findPathsByFromidandToid(fromID, toID, severPaths);
					
						//这条路的应该先不分配，看看最大能分多少
						restoreDischarge(subPath,nodes);	
						
						for (List<Integer> pathNeedtoAdjust : subPath) {
							int consumeNeed = pathNeedtoAdjust.get(pathNeedtoAdjust.size() - 1);
						
							pathNeedtoAdjust.remove(pathNeedtoAdjust.size() - 1);// 将最后的流量移除
							int maxDischarge = 0;																												
								// 找到这条路最大能提供的
							maxDischarge = maxExtraDischargePathCanAfford(pathNeedtoAdjust, nodes);// 刚开始能最大的是多少
							

							if (maxDischarge >= consumeNeed) {
								// 如果能提供的满足要求
								pathNeedtoAdjust.add(consumeNeed);// 如果能满足先满足
								// System.out.println("满足");
								for (int j = 0; j < pathNeedtoAdjust.size() - 2; j++) {// 最后一位为数字
									int require = pathNeedtoAdjust.get(pathNeedtoAdjust.size() - 1);
									nodes[pathNeedtoAdjust.get(j + 1)]
											.setDischargeTo(nodes[pathNeedtoAdjust.get(j)].getId(), require);// 应该叠加流量
								}
								
							} else {

								pathNeedtoAdjust.add(maxDischarge);
								// 这儿有一个问题，需要设置为里面容量较小的值！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
								// severPaths.get(index)中的都要变
								for (int j = 0; j < pathNeedtoAdjust.size() - 2; j++) {// 最后一位为数字
									int require = pathNeedtoAdjust.get(pathNeedtoAdjust.size() - 1);
									nodes[pathNeedtoAdjust.get(j + 1)]
											.setDischargeTo(nodes[pathNeedtoAdjust.get(j)].getId(), require);// 设置流量变小
								}

								// 这儿一定要注意，调用了最短函数之后，会修改本身的邻接矩阵
								int[][] matrix = Util.constructMatrix(nodes);
								// 服务器之间不同

								matrix[toID][fromID] = 100000;// 那么这条路不同，反着找的

								// int[] fromIDs = {
								// pathNeedtoAdjust.get(pathNeedtoAdjust.size()-2)
								// };//最后的终点
								int[] fromIDs = new int[severlocation.size()];// 终点应该是服务器点
								for (int i = 0; i < fromIDs.length; i++) {
									fromIDs[i] = severlocation.get(i);
								}

								// 该点到其他所有点的最短距离，找到该点的起始点到终点的最短距离，但是不能走之前的那条路
								List<List<Integer>> shortPaths = ssDijkstra.dijkstra_Path(matrix,
										pathNeedtoAdjust.get(0), fromIDs);
								// 该点到其他消费点最短路径，例如[43,44]
								// 新的路径
								int newDischargeNeed = consumeNeed - maxDischarge;// 还需要的路径

								int newPathToDispath = 0;// 新的线路要带的
								int dischargeCanaffort = 0;
								
								do{

									List<Integer> shortestPath = ssDijkstra.findMinPath(shortPaths);
									shortPaths.remove(shortestPath);// 删除现在的
									
									shortestPath.remove(shortestPath.size()-1);//这儿经常报错
									
									int maxDischrgeForNew = maxExtraDischargePathCanAfford(shortestPath, nodes);
									dischargeCanaffort = maxDischrgeForNew - newDischargeNeed;// 不能带完的值

									if (dischargeCanaffort > 0) {
										newPathToDispath = newDischargeNeed;
									} else {
										newPathToDispath = maxDischrgeForNew;
									}
									for (int j = 0; j < shortestPath.size() - 1; j++) {// 最后一位为数字
										nodes[shortestPath.get(j + 1)]
												.setDischargeTo(nodes[shortestPath.get(j)].getId(), newPathToDispath);// 设置流量
									}									
									// 把流量加进来
									shortestPath.add(newPathToDispath);
									// 需注意，仔细检查！！！！！！！！！！！！！！现在可以将流量加上来了
									severPaths.add(shortestPath);

									newDischargeNeed-=newPathToDispath;

								}while ((dischargeCanaffort<0)&&(shortPaths.size()!=0));
								//还是满足不了 直接安服务器  并在severPaths里面删除为了满足所做的链路
								if(dischargeCanaffort<0){
									for (int i=0;i<severPaths.size();i++) {
									  List<Integer>list=severPaths.get(i);
										if (list.get(0)==pathNeedtoAdjust.get(0)) {
											severPaths.remove(i);																						
											//流量还原
											for (int j = 0; j < list.size() - 2; j++) {// 最后一位为流量
												nodes[list.get(j + 1)]
														.plusDischarge(nodes[list.get(j)].getId(), list.get(list.size()-1));// 设置流量
											}											
										}
									}
									nodes[pathNeedtoAdjust.get(0)].setLocatedServer(true);
									severlocation.add(nodes[pathNeedtoAdjust.get(0)].getId());
									
								}

							}

						}

					}
				}

			}
//			cyclenum++;
//			if (cyclenum > 5) {// 如果循环5遍以上，则服务器点少了
//
//				System.out.println("服务器点少了");
//
//			}
//
//		} while (hasNagetive == true && cyclenum < 100);
		
		System.out.println("结果为");
		for (List<Integer> list : severPaths) {
			if(list.get(list.size()-1)!=0){
				System.out.println(list.toString());				
			}			
		}
		
		int price=0;
		for (int i = 0; i < nodes.length; i++) {
			if (nodes[i].isLocatedServer()) {
				price+=Const.SERVER_COST;
				System.out.println(i+"放服务器");
			}
		}

		price+=getPrice(severPaths,nodes);
		System.out.println(price);
		return price;
		
//		System.out.println("123");
	}

	private int getPrice(List<List<Integer>> severPaths, NetworkNode[] nodes) {
		// TODO Auto-generated method stub
		int price=0;
		for (List<Integer> list : severPaths) {
			for (int i = 0; i < list.size()-2; i++) {//最后一位是流量
				price+=(nodes[list.get(i + 1)].getLinkPrice(nodes[list.get(i)].getId()))*(list.get(list.size()-1));// 设置流量
			}
		}
						
		return price;
	}

	/**
	 * @param pathNeedtoAdjust
	 * @param nodes
	 */
	private void restoreDischarge(List<List<Integer>> subPaths, NetworkNode[] nodes) {
		// TODO Auto-generated method stub
		for (List<Integer> pathNeedtoAdjust : subPaths) {
			for (int j = 0; j < pathNeedtoAdjust.size() - 2; j++) {// 最后一位为数字
				nodes[pathNeedtoAdjust.get(j + 1)]
						.plusDischarge(nodes[pathNeedtoAdjust.get(j)].getId(), pathNeedtoAdjust.get(pathNeedtoAdjust.size()-1));// 设置流量
			}
		}
		
	}

	/**
	 * id是服务器节点，到id的流量设为满足要求的
	 * 
	 * @param paths
	 * @param nodes
	 * @param id
	 * @param matrix
	 */
	public void setDischarge(List<List<Integer>> severPaths, NetworkNode[] nodes, ConsumeNode[] consumeNodes,
			List<Integer> severGroup) {
		for (List<Integer> list : severPaths) {// 该服务器连接的点
			list.remove(list.size() - 1);// 最后一个是最短距离
			// 注意这儿将需要的流量加进来了！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！1！！！！！！！
			int discharge = consumeNodes[nodes[list.get(0)].getComsumeNodeId()].getRequired();
			list.add(discharge);
			for (int j = 0; j < list.size() - 2; j++) {
				int require = consumeNodes[nodes[list.get(0)].getComsumeNodeId()].getRequired();
				nodes[list.get(j + 1)].setDischargeTo(nodes[list.get(j)].getId(), require);// 设置流量
				// list.add(require);
			}			
		}
	}

	/**
	 * 根据起始点和终点 找到经过的左右的路线
	 * 
	 * @param fromid
	 * @param toid
	 * @param paths
	 * @return
	 */
	private List<List<Integer>> findPathsByFromidandToid(int fromid, int toid, List<List<Integer>> paths) {
		List<List<Integer>> subPath = new ArrayList<>();

		for (int i = 0; i < paths.size(); i++) {
			if (paths.get(i).contains(fromid) && paths.get(i).contains(toid)) {
				if (paths.get(i).get(paths.get(i).size() - 1) == fromid
						|| paths.get(i).get(paths.get(i).size() - 1) == toid) {

				} else {
					subPath.add(paths.get(i));
				}

			}
		}

		return subPath;
	}

	/**
	 * 找到这条线路里面能承受的最大值
	 * 
	 * @param path
	 * @param nodes
	 * @return
	 */
//	private int maxDischargePathCanAfford(List<Integer> path, NetworkNode[] nodes) {
//		List<Integer> maxDischarge = new ArrayList<>();
//		for (int i = 0; i < path.size() - 1; i++) {// 最后一位
//			maxDischarge.add(nodes[path.get(i + 1)].getMaxDischarge(nodes[path.get(i)].getId()));
//		}
//		return findMin(maxDischarge);
//
//	}

	/**
	 * 最大的剩余流量
	 * 
	 * @param path
	 * @param nodes
	 * @return
	 */
	private int maxExtraDischargePathCanAfford(List<Integer> path, NetworkNode[] nodes) {
		List<Integer> maxDischarge = new ArrayList<>();
		for (int i = 0; i < path.size() - 1; i++) {// 最后一位已经去除
			maxDischarge.add(nodes[path.get(i + 1)].getExtraDischarge(nodes[path.get(i)].getId()));
		}
		if (findMin(maxDischarge) > 0) {
			return findMin(maxDischarge);
		} else {
			return 0;
		}

	}

	/**
	 * 找到最小值
	 * 
	 * @param max
	 * @return
	 */
	private int findMin(List<Integer> max) {
		int min = 1000000;
		for (int i : max) {
			if (i < min) {
				min = i;
			}
		}
		return min;
	}

}
